package com.cheung.leetcode.dp;

import org.junit.jupiter.api.Test;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.dp
 * @Author :  cheungming
 * @CreateTime : 2024-06-14 08:31:43
 * @Description : 目标和
 * @Version : 1.0
 */
public class Code494Test {

    public int findTargetSumWays(int[] nums, int target) {
        // nums的目标和target = (m项相加)- (n-m项相加) = left - right
        // 而nums的和sum = left + right, 所以left = (sum + target) / 2
        // sum和target都是确定的，因此可以用背包问题求解，即求nums数组中有多少种组合，使得组合的和等于left
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 如果sum小于target或者(sum + target) % 2 == 1，则无法凑出target
        if (sum < target || (sum + target) % 2 == 1) {
            return 0;
        }
        int left = (sum + target) / 2;
        // nums是非负数组，因此left >= 0
        if (left < 0) {
            return 0;
        }
        int[] dp = new int[left + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[left];

    }

    @Test
    public void test1() {
        assert findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3) == 5;
    }

    @Test
    public void test2() {
        assert findTargetSumWays(new int[]{1}, 1) == 1;
    }

    @Test
    public void test3() {
        assert findTargetSumWays(new int[]{100}, -200) == 0;
    }
}
